package 链表;

/**
 * 给定一个链表，判断链表中是否有环。
 * <p>
 * 操场跑圈，只要是环总会相遇的
 * https://leetcode-cn.com/problems/linked-list-cycle/
 */
public class _141_环形链表 {

    public static void main(String[] args) {
        ListNode first = new ListNode(10);
        ListNode second = new ListNode(11);
        ListNode third = new ListNode(12);
        ListNode four = new ListNode(13);
        ListNode five = new ListNode(14);
        first.next = second;
        second.next = third;
        third.next = four;
        four.next = five;
        System.out.println(hasCycle(first));
        five.next = first;
        System.out.println(hasCycle(first));
    }

    /**
     * 快慢指针解法
     */
    public static  boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            System.out.println("slow :" + slow.val + ",quick: " + fast.val);
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
}
